package com.ljx.offer;

import org.junit.Test;

/**
 * @author 李捷禧
 * Date: 2023/3/30
 * ClassName: C_47
 */

public class C_47 {
    /**
     * 每个数存储它得到最大可能得值
     * 输出右下角的值
     * @param grid
     * @return
     */
    public int maxValue(int[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if(i == 0 && j ==0) continue;
                else if(i == 0) grid[i][j] += grid[i][j-1];
                else if(j == 0) grid[i][j] += grid[i-1][j];
                else grid[i][j] += Math.max(grid[i][j-1],grid[i-1][j]);
            }
        }
        return grid[grid.length-1][grid[0].length-1];
    }

    @Test
    public void test(){
        int[][] arr = new int[][]{{1,2,5},{3,2,1}};
        System.out.println(maxValue(arr));

    }
}
